package Hot100;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2022-01-07 15:07
 */
public class lengthOfLIS300 {

    /**
     * 300. 最长递增子序列
     * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序
     * 1、dp，dp[i]表示以i为结尾的最长递增子序列的长度，在i前面的元素中找到比i小的元素，将其+1，找出所有组合中最大的
     *
     * */
    public int lengthOfLIS(int[] nums) {
        if (nums.length<=1) return nums.length;
        int n=nums.length;
        int[] dp=new int[n];
        Arrays.fill(dp,1);
        int res=1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <i ; j++) {
                if (nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            res=Math.max(res,dp[i]);
        }
        return res;
    }
}
